\documentclass{article}
\usepackage{amsmath,amsfonts}
\usepackage{latexsym}
\usepackage{bbm}
\usepackage[pdftex]{graphicx}
\usepackage[framed,numbered]{mcode} % MATLAB code typesetting package (credit: Florian Knorn)
\usepackage{float}

\marginparwidth 0pt
\oddsidemargin  0pt
\evensidemargin  0pt
\marginparsep 0pt
\topmargin   0pt
\textwidth   6.0in
\textheight  8.5in

\begin{document}

\begin{flushright}
{\bf Andrew Ziegler\\Siva Subramaniam\\
May 23, 2011\\
CSE 252C\\
Assignment \#1\\
}
\end{flushright}

Note: All Matlab code was typeset using \cite{lib:mcode}

\begin{enumerate}
\item Handwritten Digits.
\begin{enumerate}
\item Download the MNIST training and testing data from http://yann.lecun.com/exdb/mnist.
\lstinputlisting{"problem1/getMNIST.sh"}
\item Write a utility to extract the images (of size $28\times 28$) and labels ($0,\ldots,9$).  Use it to import the first $M=2000$ training digits and the first $N=1000$ testing digits.
\lstinputlisting[firstline=2, lastline=7]{"problem1/problem1_1.m"}
\lstinputlisting{"problem1/getMNISTDigits.m"}
\lstinputlisting{"problem1/extractLabels.m"}
\lstinputlisting{"problem1/extractDigits.m"}
\item Display the first 40 training digits together with their labels, arranged in a $4\times 10$ array.
\\
See Figure 1 for result.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%MOVE THIS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure}[H] %b=bottom t=top
	\begin{center}
	\includegraphics[width=.52\linewidth]{problem1/img0.jpg}
	\caption{The first 40 training digits with their labels.}
	\end{center}
	\label{prob1}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\lstinputlisting[firstline=8, lastline=10]{"problem1/problem1_1.m"}
\lstinputlisting{"problem1/arrangeInGrid.m"}
\item Compute the prior probability of each digit in the training set.  Is it uniform?.
\\
\begin{table}[H]
\begin{center}\begin{tabular}{ | l | l |}
	\hline
	Digit & Prior Probability \\
	\hline
	0 & 0.096\\
	\hline
	1 & 0.110\\
	\hline
	2 & 0.099\\
	\hline
	3 & 0.096\\
	\hline
	4 & 0.107\\
	\hline
	5 & 0.090\\
	\hline
	6 & 0.100\\
	\hline
	7 & 0.112\\
	\hline
	8 & 0.086\\
	\hline
	9 & 0.105\\
	\hline
    \end{tabular}\end{center}
    \caption{The prior probabilities of the digits in the training set with M=2000.}
    \end{table}
 The prior probabilities of the digits is roughly uniform, as is apparent in Table 1.
 \lstinputlisting[firstline=11, lastline=25]{"problem1/problem1_1.m"}
\end{enumerate}

\item Measuring Similarity/Dissimilarity.

Let $\boldsymbol{x}^i\in\mathbb{R}^d$ (with $d=28^2$) denote the $i$th training example concatenated as a column vector.
\begin{enumerate}
\item Implement the following pairwise comparison functions of the form ${\mathcal D}(\boldsymbol{x}^i,\boldsymbol{x}^j)$:
\begin{itemize}
\item $L_p$ norm: $\left(\sum_{k=1}^d|x_k^i-x_k^j|^p\right)^{1/p}$
\lstinputlisting{"problem2/lpNorm.m"}
\item Inner product: $(\boldsymbol{x}^i)^\top\boldsymbol{x}^j$
\item Normalized inner product: $(\boldsymbol{x}^i)^\top\boldsymbol{x}^j/\|\boldsymbol{x}^i\|\|\boldsymbol{x}^j\|$
\lstinputlisting{"problem2/dotProduct.m"}
\item $\chi^2$ distance: $\frac{1}{2}\sum_{k=1}^d(x_k^i-x_k^j)^2/(x_k^i+x_k^j)$
\lstinputlisting{"problem2/chiSquared.m"}
\end{itemize}
Each is defined for $\boldsymbol{x}\in{\mathbb R}^d$ except $\chi^2$, which requires $\boldsymbol{x}$ to be nonnegative and sum to 1.
\item Compute and display the best match (using max or min as appropriate) for the first 10 training digits (excluding self matches) vs.~all $M$ training digits using $L_1$, $L_2$, $L_\infty$, and inner product (both normalized and raw).  Use an asterisk to indicate errors.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%MOVE THIS%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
\begin{figure}[t] %b=bottom t=top
\begin{tabular}{c}
		\includegraphics[width=.5\linewidth]{problem2/img0.jpg}
		\includegraphics[width=.5\linewidth]{problem2/img1.jpg}\\
	\end{tabular}
	\caption{TODO}
	\label{text_book}
\end{figure}
\end{center}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Which choice of ${\mathcal D}(\cdot,\cdot)$ gave the fewest errors?  Which gave the most?
\end{enumerate}

\item Confusion Matrices and ROC Curves.
\begin{enumerate}
\item Compute the $L_2$ distance from all $N$ testing digits to all $M$ training digits.
\item Assuming a 1-nearest neighbor classifier, compute the $10\times 10$ confusion matrix for this experiment. 
Display it as an image and comment on what it reveals about the classification behavior for digits such as 5 and 8.
\item Compute the histogram of distances for genuine matches and for impostors.  Use bins of size 10 on the range 0 to 250, and normalize the histograms to sum to 1.  Plot the two histograms on the same set of axes.
\item Plot the ROC curve for this experiment.  What is the equal error rate?
\end{enumerate}

\item Color Histogram Matching.
\begin{enumerate}
\item Select 10 objects from the Amsterdam Library of Object Images (ALOI) at http://staff.
science.uva.nl/$\sim$aloi.  For each object, download two images captured by the same camera under different illumination directions; call the resulting two sets of images $\mathcal A$ and $\mathcal B$.  The preview thumbnail resolution of $154\times 115$ is sufficient for this exercise.
\item For each of the 20 downloaded images, compute the color histogram using a color space of your choice with 15 equally spaced bins per channel.
\item Compute the $10\times 10$ matrix of $\chi^2$ distances between the color histograms from $\mathcal A$ to those of $\mathcal B$.  Display the distance matrix, indicating the best matching entry in each row.  Comment on the performance you observe, highlighting interesting successes or failures.
\end{enumerate}

\end{enumerate}

\bibliographystyle{plain} \bibliography{bibfile}

\end{document}







